import java.util.ArrayList;
import java.util.List;

//电话号码的字母组合
//测试链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
public class LetterCombinations {
    String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> ans;
    StringBuilder path;
    public List<String> letterCombinations(String digits) {
        ans = new ArrayList<>();
        path = new StringBuilder();

        if(digits == null || digits.length() == 0) return ans;
        dfs(digits.toCharArray(), 0);
        return ans;
    }

    void dfs(char[] digits, int pos) {
        if(pos == digits.length) {
            ans.add(path.toString());
            return;
        }
        System.out.println(digits[pos]);
        int index = digits[pos] - '0'; //当前位置的数字号码
        String s = map[index]; //拿到每个数字对应的字符串
        char[] arr = s.toCharArray();
        for(int i = 0; i < arr.length; i++) {
            path.append(arr[i]);
            dfs(digits,pos+1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
